package primary.primary0;

import java.util.ArrayList;
import java.util.List;

/**
 * 和剑指offer的spiralOrder一样
 */
public class S0054螺旋矩阵 {
    class Solution {
        /**
         * 100
         * 如果按照方向+碰到边界就转头的话，会需要一个visited矩阵，然后最后怎么停止好像也有点恶心
         * 所以直接一圈一圈访问吧
         */
        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> result = new ArrayList<>();
            for(int i = 0; i < (matrix.length + 1)/2 && i < (matrix[0].length+1)/ 2; i++){
                recordCircle(matrix, i, result);
            }
            return result;
        }

        public void recordCircle(int[][] matrix, int curCircle, List<Integer> result){
            for(int i = curCircle; i <= matrix[0].length - curCircle - 1; i++){
                result.add(matrix[curCircle][i]);
            }
            for(int i = curCircle + 1; i <= matrix.length - curCircle - 1; i++){
                result.add(matrix[i][matrix[0].length - curCircle - 1]);
            }
            // 右下到左下 以及 左下到左上，判断一下是否存在
            //
            if(!(matrix.length % 2 == 1 && curCircle == matrix.length / 2)){
                for(int i = matrix[0].length - curCircle -1 - 1; i >= curCircle; i --){
                    result.add(matrix[matrix.length - curCircle - 1][i]);
                }
            }
            if(!(matrix[0].length % 2 == 1 && curCircle == matrix[0].length / 2)){
                for(int i = matrix.length - curCircle - 1 - 1; i >= curCircle + 1; i --){
                    result.add(matrix[i][curCircle]);
                }
            }

        }
    }


    /**
     * 答案，方向+访问记录矩阵
     * 然后如何判断走完了，是按照总步数来判断的
     * 然后如何判断掉头，是按照下一个位置越界来做的
     */
    class Solution2 {
        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> order = new ArrayList<Integer>();
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return order;
            }
            int rows = matrix.length, columns = matrix[0].length;
            boolean[][] visited = new boolean[rows][columns];
            int total = rows * columns;
            int row = 0, column = 0;
            int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            int directionIndex = 0;
            for (int i = 0; i < total; i++) {
                order.add(matrix[row][column]);
                visited[row][column] = true;
                int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
                if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                    directionIndex = (directionIndex + 1) % 4;
                }
                row += directions[directionIndex][0];
                column += directions[directionIndex][1];
            }
            return order;
        }
    }


    /**
     * 逐层输出
     */
    class Solution3 {
        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> order = new ArrayList<Integer>();
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return order;
            }
            int rows = matrix.length, columns = matrix[0].length;
            int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
            // 这里逐层挺好
            while (left <= right && top <= bottom) {
                for (int column = left; column <= right; column++) {
                    order.add(matrix[top][column]);
                }
                for (int row = top + 1; row <= bottom; row++) {
                    order.add(matrix[row][right]);
                }
                // 避免重复走
                if (left < right && top < bottom) {
                    for (int column = right - 1; column > left; column--) {
                        order.add(matrix[bottom][column]);
                    }
                    for (int row = bottom; row > top; row--) {
                        order.add(matrix[row][left]);
                    }
                }
                left++;
                right--;
                top++;
                bottom--;
            }
            return order;
        }
    }


}
